package Sort;

public class QuickSort {
    //快速排序
    public static void main(String[] args) {
        int[] arr={1,9,5,7,6,8,2,3,4,2,0,6};
        quickSort(arr,0,arr.length-1);
        printarr(arr);
    }

    private static void quickSort(int[] arr,int i,int j) {
        //确定基准值的位置
        int start=i;
        int end=j;

        if(start>end){
            return;
        }
        //索引0为基准值
        int basic=arr[i];

        while (start!=end) {
            while(true){
                if (end<=start || arr[end]<basic) {
                    break;
                }
                end--;
            }
            while(true){
                if (end<=start || arr[start]>basic) {
                    break;
                }
                start++;
            }
            int temp=arr[start];
            arr[start]=arr[end];
            arr[end]=temp;
        }
        //基准值归位
        int temp=arr[start];
        arr[start]=arr[i];
        arr[i]=temp;
        //递归
        //左边
        quickSort(arr,i,start-1);
        //右边
        quickSort(arr,end+1,j);
    }


    public static void printarr(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}
